package com.zq.solution.algorithm.sort;

/**
 * @ClassName ShellSort 希尔排序
 * @Description 希尔排序(Shell’s Sort)是插入排序的一种，是直接插入排序算法的一种更高版本的改进版本
 * 排序思想：
 *   1.把记录按步长gap分组，对每组记录采用直接插入排序方法进行排序；
 *   2.随着步长逐渐减小，所分成的组包含的记录越来越多；
 *   3.当步长值减小到1时，整个数据合成一组，构成一组有序记录，完成排序；
 * @Author ZQ
 * @Date 2020/11/4 10:56
 * @Version V1.0
 **/
public class ShellSort {
    public static int[] baseInsertSort(int[] a){//直接插入排序
        if (a == null || a.length < 2) return a;
        for (int i = 1; i < a.length; i++){
            int j = i;
            int tmp = a[i];
            while (j > 0 && tmp < a[j - 1]){
                a[j] = a[j - 1];
                j--;
            }
            a[j] = tmp;
        }
        return a;
    }


    public static int[] shellSort(int[] arr){
        //初始化增量
        int h = 1;
        //计算最大间隔，公式：h = h * 3 + 1
        while(h < arr.length / 3){
            h = h * 3 + 1;
        }
        //缩小增量进行排序
        while(h > 0){
            //进行插入排序
            int waitInsert;			//等待插入的数
            int i,j;				//i表示当前待插入数下标；j表示本次被比较的有序数位置
            for(i = h; i < arr.length; i++) {
                waitInsert = arr[i];	//得到本轮待插入的数
                j = i - h;				//比较位置初始化，也就是有序序列的最后一个位置，从后往前
                //若大于或等于等待插入的数值大小，则该数右移一个间隔大小，然后进行下一次比较
                while(j > -1 && arr[j] >= waitInsert) {
                    arr[j + h] = arr[j];
                    j = j - h;
                }
                //插入的位置一定是上一次比较的数的位置，也就是j+h的位置。（注意到j-h的时机即可理解）
                arr[j + h] = waitInsert;
            }
            //缩小增量，公式：h = (h - 1) /3
            h = (h - 1) / 3;
        }
        return arr;
    }


    public static void main(String[] args) {
        int[] a = new int[]{6,71,72,8,73,75,14,80,18,83,20,87,24,25,27,93,29,97,99,100,37,102,103,42,107,47,112};
        for (Integer num : shellSort(a)){
            System.out.print(num + " ");
        }
        System.out.println();
        int[] b = new int[]{6,71,72,8,73,75,14,80,18,83,20,87,24,25,27,93,29,97,99,100,37,102,103,42,107,47,112};
        for (Integer num : baseInsertSort(b)){
            System.out.print(num + " ");
        }
    }

}
